package 图.并查集;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.PriorityQueue;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/8 19:49
 */
public class lc200岛屿问题 {

    /*
     毫无疑问这道题,是非常经典的 DFS , BFS, 并查集 练习题

     **这个 题解下面有练习的题单!**
        https://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

     - 淹没法
     - 感染法
     */


    //用 BFS 来实现一下!

    /*
    下面这句话 去理解一下:
     不少同学用广搜做这道题目的时候，超时了。 这里有一个广搜中很重要的细节：

    根本原因是只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。

    很多同学可能感觉这有区别吗？

    如果从队列拿出节点，再去标记这个节点走过，就会发生下图所示的结果，会导致很多节点重复加入队列。
     */
    int direction[][] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public int solve(int martix[][]) {
        int ans = 0;
        for (int i = 0; i < martix.length; i++) {
            for (int j = 0; j < martix[0].length; j++) {
                if (martix[i][j] != 0) {
                    ans++;
                    bfs(martix, i, j);
                }
            }
        }
        return ans;
    }

    public void bfs(int martix[][], int i, int j) {

        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{i, j});
        martix[i][j] = 0;
        while (!queue.isEmpty()) {
            int[] remove = queue.remove();
//            martix[remove[0]][remove[1]] = 0;  // 感染掉
            for (int dir[] : direction) {
                int _x = dir[0] + remove[0];
                int _y = dir[1] + remove[1];
                if (_x < 0 || _y < 0 || _x == martix.length || _y == martix[0].length || martix[_x][_y] == 0) {
                    continue;
                }
                queue.addLast(new int[]{_x, _y});
                martix[_x][_y] = 0;
            }
        }
    }

    //dfs
    public int solve1(int martix[][]) {
        int ans = 0;
        boolean vis [][] = new boolean[martix.length][martix[0].length];
        for (int i = 0; i < martix.length; i++) {
            for (int j = 0; j < martix[0].length; j++) {
                if (martix[i][j] != 0 && !vis[i][j]) {
                    ans++;
//                    bfs(martix, i, j);
                    dfs(i,j,martix,vis);
                }
            }
        }
        return ans;
    }

    public void dfs(int i, int j, int matrix[][], boolean[][] vis) {
        if (i < 0 || j < 0 || i == matrix.length || j == matrix[0].length || vis[i][j] || matrix[i][j] == 0) {
            return;
        }
        vis[i][j] = true;
        dfs(i - 1, j, matrix, vis);
        dfs(i + 1, j, matrix, vis);
        dfs(i, j - 1, matrix, vis);
        dfs(i , j + 1, matrix, vis);
    }



}
